#include <stdio.h>
#include <stdlib.h>

/* 链表 */
typedef struct _Node
{
    int data;
    struct _Node *prev;
    struct _Node *next;
} Node;
typedef Node List;

void initList(List *list)
{
    list->prev = list;
    list->next = list;
}

void addBack(List *list, int data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;

    p->next = list;
    p->prev = list->prev;
    list->prev->next = p;
    list->prev = p;
}

void removeNode(Node *p)
{
    p->next->prev = p->prev;
    p->prev->next = p->next;
    free(p);
}

int isEmptyList(List *list)
{
    return list == list->next && list == list->prev;
}

int getListSize(List *list)
{
    int n = 0;
    for (Node *p = list->next; p != list; p = p->next) {
        n++;
    }
    return n;
}

void removeList(List *list)
{
    while (!isEmptyList(list)) {
        removeNode(list->prev);
    }
}

/* 栈 */
typedef struct {
    List list;
} Stack;

void initStack(Stack *s)
{
    initList(&s->list);
}

int isEmptyStack(Stack *s)
{
    return isEmptyList(&s->list);
}

void push(Stack *s, int data)
{
    addBack(&s->list, data);
}

int getTop(Stack *s)
{
    if (!isEmptyStack(s)) {
        return s->list.prev->data;
    } else {
        return -1;  // 无效值
    }
}

void pop(Stack *s)
{
    if (!isEmptyStack(s)) {
        removeNode(s->list.prev);
    }
}

int getStackSize(Stack *s)
{
    return getListSize(&s->list);
}

void showStack(Stack *s)
{
    List *list = &s->list;
    printf("Size:%d Data:", getListSize(list));
    printf("[BASE]");
    for (Node *p = list->next; p != list; p = p->next) {
        printf(" %d", p->data);
    }
    printf(" [TOP]\n");
}

void removeStack(Stack *s)
{
    removeList(&s->list);
}

void testStack(void)
{
    Stack s;
    initStack(&s);
    push(&s, 1);
    push(&s, 10);
    push(&s, 100);
    showStack(&s);
    pop(&s);
    showStack(&s);
    removeStack(&s);
    showStack(&s);

    push(&s, 1);
    push(&s, 10);
    push(&s, 100);
    showStack(&s);

    for (int i = 0; i < 10; i++) {
        push(&s, i);
    }

    showStack(&s);

    for (int i = 0; i < 10; i++) {
        pop(&s);
    }
    showStack(&s);

    removeStack(&s);
}

int main(int argc, char *argv[])
{
    testStack();
    return 0;
}
